\documentclass{book}
\usepackage{graphicx}
\usepackage{amsmath}

\begin{document}
\section*{Question 1}
\subsection*{(A)}
$ T(n) = 4T(\frac{n}{2})+1 \\
Master Method: T(n)=aT(\frac{n}{b}) + f(n) \\
n^{\log_b a} = n^{\log_2 4} = n^2 \\
\frac{1}{n^2} = n^{-1} \in O(n^{- \epsilon}) \\
T(n) \in \theta (n^2) \\
$
\subsection*{(B)}
$T(n) = 4T(\frac{n}{2}) + n^2 \\
Master Method: T(n)=aT(\frac{n}{b}) + f(n) \\
n^{\log_a b} = n^{log_2 4} = n^2 \\
\frac{n^2}{n^2} = \theta(1) \\
T(n) \in \theta (n^2 \log n) \\
$
\subsection*{(C)}
$T(n) = 4T(\frac{n}{2}) + n^4 \\
Master Method: T(n)=aT(\frac{n}{b}) + f(n) \\
n^{\log_a b} = n^{log_2 4} = n^2 \\
\frac{n^4}{n^2} = \theta(n^2) \in \theta (n^{\epsilon}) \\
T(n) \in \theta (n^4) \\
$
\subsection*{(D)}
$ T(n) = 3T(\frac{n}{9}) + \sqrt{n} \\
Master Method: T(n)=aT(\frac{n}{b}) + f(n) \\
n^{\log_b a} = n^{\log_3 9} = n^2 \\
\frac{n^2}{n^{0.5}} = n^{1.5} \in \theta (n^{\epsilon}) \\
T(n) \in \theta (n^2) \\
$
\subsection*{(E)}
$
$
\section*{Question 2}
\subsection*{(A)}
\subsection*{(B)}
\section*{Question 3}
Prove $f(n) \in O(g(n))$ then $f(n) + g(n) = \theta (g(n))$ \\
$O(g) = \{f | \exists c, n_0 > 0 \bullet \forall n \geq n_0 \bullet 0 \leq f(n) \leq c \cdot g(n)\} \\
\theta(g) = \{f| \exists c_1, c_2, n_0 > 0 \bullet \forall n \geq n_0 \bullet 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \} $ 
\section*{Question 4}
\subsection*{(A)}
\subsubsection*{(i)}
$T(n) = T(\frac{n}{2}) + 1 \\
\frac{1}{n^0} = \frac{1}{1} = 1 \\
T(n) \in \theta (\log n) \\
$
\subsubsection*{(ii)}
$T(n) = T(\frac{n}{2}) + n \\
\frac{n}{n^0} = \frac{n}{1} = n \in \theta (n^{\epsilon}) \\
T(n) \in \theta (n) \\
$
\subsubsection*{(iii)}
$T(n) = T(\frac{n}{2}) + \\
$
\subsection*{(B)}
\subsubsection*{(i)}
\subsubsection*{(ii)}
\subsubsection*{(iii)}
\section*{Question 5}

\end{document}